// LRUCache.h
// LRUCache based on http://www.flipcode.com/archives/LRU_Cache.shtml
//
#ifndef	LRUCACHE_H
#define LRUCACHE_H

//template<typename KEY, typename VALUE, int SIZE = 8>
//class LRUCache
//{
//public:
//	struct  cacheSlot
//	{
//		KEY   key;
//		VALUE val;
//	};
//
//private:
//#ifdef _DEBUG
//public:
//#endif
//	int size;
//	unsigned int   index;        //  We will use this to store the order in 1 based nibbles.
//	//  0 will be used for unasigned cache slots
//	//  We will store de most recent accesed index on the least 
//	//  significant bit.
//	cacheSlot  cache[SIZE];
//
//public:
//	// --------------------------------------------------------------------------------------------
//	LRUCache  ()  : index(0), size(0) {memset(cache,0,sizeof(cacheSlot)*SIZE);}
//
//	// --------------------------------------------------------------------------------------------
//	inline  void  reset   (){index=0; memset(cache,0,sizeof(cacheSlot)*SIZE);}
//
//	// --------------------------------------------------------------------------------------------	
//	inline  bool  find    (const  KEY& _key, VALUE& val_)
//	{
//		unsigned int   msc = 0xffffffff; // auxiliary value we need to move one nibble from the middle
//		// of the dword to the begining 
//		unsigned int  idx = index;
//		cacheSlot* ptr = (cache-1);  // prepare to access on 1 based index's
//
//		bool found = false;
//		while( idx )
//		{
//			unsigned int hit = idx&0xf;
//			//assert(hit<=8);
//			if(hit == 0)
//			{
//				int x = 0;
//			}
//			
//
//			msc<<=4;
//			if(ptr[hit].key == _key)
//			{
//				//  key found, we move it to the "begining" so we find it faster next time.
//				index = (index&msc) | ( (index<<4)&(~msc) ) | hit;
//
//				if( ((unsigned int)index&0xf) == 0)
//					int a = 0;
//
//				val_  = ptr[hit].val;
//				found = true;
//				break;
//			}
//			idx>>=4;
//		}
//		
//		return found;
//	}
//
//	// --------------------------------------------------------------------------------------------
//	inline  VALUE  insert  (const  KEY& _key, const VALUE& _val)
//	{
//		cacheSlot* ptr = cache-1;    // prepare to access on 1 based index's
//		unsigned int hit = index>>28;  // we remove the most significant nibble from the index table
//		if(!hit)    //  only when filling de cache.
//		{
//			hit = 1;
//			unsigned int idx = index;
//			while( ((unsigned int)idx&0xf) )  { idx>>=4, ++hit; }
//			//assert(hit<=SIZE);
//		}
//		
//		
//		VALUE ret = ptr[hit].val;
//	
//		ptr[hit].key = _key;
//		ptr[hit].val = _val;
//		index = (index<<4) | hit;
//		
//		size++;
//		return ret;
//	}
//
//	// --------------------------------------------------------------------------------------------
//	inline  void  remove(const  KEY& _key)
//	{
//		//unsigned int   msc = 0xffffffff; // auxiliary value we need to move one nibble from the middle
//		//// of the dword to the begining 
//		//unsigned int  idx = index;
//		//cacheSlot* ptr = (cache-1);  // prepare to access on 1 based index's
//
//		//unsigned int hit;
//		//bool found = false;
//		//while( idx )
//		//{
//		//	hit = idx&0xf;
//		//	//assert(hit<=8);
//		//	msc<<=4;
//		//	if(ptr[hit].key == _key)
//		//	{
//		//		//  key found, we move it to the "begining" so we find it faster next time.
//		//		index = (index&msc) | ( (index<<4)&(~msc) ) | hit;
//		//		index >>= 4;
//		//		index = index | (hit<<60);
//		//		//val_  = ptr[hit].val;
//		//		found = true;
//		//		break;
//		//	}
//		//	idx>>=4;
//		//}
//
//
//		//if(found)
//		//{
//		//	// remove item
//		//	//index>>=4;
//		//
//		//	// empty memory
//		//	memset(&ptr[hit], 0, sizeof(cacheSlot) );
//		//	size--;
//		//}
//	}
//
//};

#include <map>
#include <list>
#include <vector>

template <typename K,typename T, int Capacity>
class LRUCache
{
private:
	std::list<K>	entries;
	std::map<K, T>	map;
public:
	int reqCount;
	int missCount;

	LRUCache()  { reset();}
	~LRUCache() { reset();}

	// --------------------------------------------------------------------------------------------
	T insert(const  K& _key, const T& _val)
	{
		// find the key
		std::map<K,T>::iterator it = map.find(_key);
		if( it == map.end() )
		{
			// insert a new entry
			// push front the key of the most recentely used entry
			entries.push_front(_key);
			map[_key] = _val;
		}
		else
		{
			// remove from current position
			entries.remove(_key);
			
			// re-insert at the beginning
			entries.push_front(_key);
			
			// update its pointer
			//map[key] = entries.begin();
		}
		
		T ret = 0;
		if(map.size() > Capacity)
		{
			// get the less recent used key
			K lru = entries.back();
			
			// store the item
			ret   = map[lru];
			
			// adjust size by removing lru
			entries.pop_back();
			map.erase(lru);
		}
		return ret;
	}

	// --------------------------------------------------------------------------------------------
	void use(const K &key)
	{
		entries.remove(key);
			
		// re-insert at the beginning
		entries.push_front(key);	
	}
	
	// --------------------------------------------------------------------------------------------
	bool find(const K &key)
	{
		return map.find(key) != map.end();
	}

	// --------------------------------------------------------------------------------------------
	T remove(const K &key)
	{
		T ret = 0;
		if( find(key) )
		{
			ret = map[key];
			
			map.erase(key);
			entries.remove(key);
		}

		return ret;
	}

	// --------------------------------------------------------------------------------------------
	// returns a copy of current entries
	std::vector<T> getEntries()
	{
		std::vector<T> v;
		for(std::map<K, T>::iterator it = map.begin();
			it != map.end();
			++it)
			v.push_back(it->second);

		return v;
	}


	// --------------------------------------------------------------------------------------------
	void reset()
	{
		entries.clear();
		map.clear();
	}
};


#endif
